|
In computer science, patience sorting is a sorting algorithm inspired by, and named after, the card game patience. Patience sorting has the property of being able to efficiently compute the length of a longest increasing subsequence in a given array. ==Overview== The algorithm's name derives from a simplified variant of the patience card game. This game begins with a shuffled deck of cards. These cards are dealt one by one into a sequence of piles on the table, according to the following rules. # Initially, there are no piles. The first card dealt forms a new pile consisting of the single card. # Each subsequent card is placed on the leftmost existing pile whose top card has a value no greater than the new card's value, or to the right of all of the existing piles, thus forming a new pile. # When there are no more cards remaining to deal, the game ends. This card game is turned into a two-phase sorting algorithm, as follows. Given an array of elements from some totally ordered domain, consider this array as a collection of cards and simulate the patience sorting game. When the game is over, recover the sorted sequence by repeatedly picking off the minimum visible card; in order words, perform an of the piles, each of which is internally sorted. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Patience sorting」の詳細全文を読む スポンサード リンク
|